/**
 * [1,n]之间数位互异的数的数量
 * 
 * 一共10个数字，显然用二进制状压
 * Dij表示当前数位i、出现过的数字情况为j的目标
 */
using llt = long long;

vector<int> G;
// Dij表示搜索到i位当前数字出现的情况为j的数量
llt D[12][1024];
llt dfs(int pos, int st, bool lead, bool limit){
    if(-1 == pos) {
        return lead ? 0 : 1;   // 纯0不算
    }
    if(not lead and not limit and -1 != D[pos][st]) {
        return D[pos][st];
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(i == 0 and lead){ // 前导0不能计算
            ans += dfs(pos - 1, st, true, limit&&i==last);
        }else if(0 == (st & (1 << i))){
            ans += dfs(pos - 1, st | (1 << i), false, limit&&i==last);
        }
    }
    if(not lead and not limit){
        D[pos][st] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int countSpecialNumbers(int n) {
        memset(D, -1, sizeof(D));
        return digitDP(n);
    }  
};
